package com.cqs.leetcode.graph;

import com.cqs.leetcode.Node;
import com.google.common.collect.Lists;

import java.util.*;

public class CloneGraph133 {
    public Node cloneGraph(Node node) {
        if(node == null) return null;
        Queue<Node> q = new LinkedList<>();
        q.add(node);
        Set<Integer> set = new HashSet<>();
        Node g = null;
        Map<Integer,Node> map = new HashMap<>();
        while(q.size() > 0){
            node = q.poll();
            //防止重复处理节点
            if(set.contains(node.val)) continue;
            set.add(node.val);
            //复制当前节点
            Node t = map.computeIfAbsent(node.val, k -> new Node(k));
            if(g == null) g = t;
            List<Node> list = new ArrayList<>();
            for(Node n: node.neighbors){
                Node ns = map.computeIfAbsent(n.val, k -> new Node(k));
                list.add(ns);
            }
            t.neighbors = list;
            q.addAll(node.neighbors);
        }
        return g;
    }

    public static void main(String[] args) {
        CloneGraph133 graph = new CloneGraph133();
        Node n1 = new Node();
        n1.val = 1;
        Node n2 = new Node();
        n2.val = 2;
        n1.neighbors = Lists.newArrayList(n2);
        n2.neighbors = Lists.newArrayList(n1);
        Node node = graph.cloneGraph(n1);
        System.out.println(node);
    }
}
